The invention is based on a priority application EP08290625.6 which is hereby incorporated by reference.
The present invention relates to a method of providing a successor list for routing in a peer-to-peer overlay network, and a network node and a computer program product to execute said method.
Peer-to-peer (=P2P) overlay networks are used for a broad number of applications such as VoIP (e.g., Skype) or file-sharing (e.g., eMule) (VoIP=Voice over Internet Protocol). Features like high scalability, self-organisation and fault tolerance are achieved by a distributed architecture and data storage on collectively provided and used resources. The P2P network consists of nodes acting as peers, i.e., both as clients and as servers of the network. In the following description, the terms “node” and “peer” are used interchangeably. Each node of the network maintains one or more logical links to other nodes that are established with respect to an overlay algorithm and used for message transmission.
State-of-the-art P2P networks build a logical topology structure based on overlay specific algorithms that are agnostic of the underlying network infrastructure. Each node maintains one or more links to other nodes that are used for message routing in a broadcast manner (unstructured overlays, e.g. Gnutella) or in an ID-based manner (structured overlays using a Distributed Hash Table (=DHT), e.g. Chord) (ID=identification/identifier). Some systems use hybrid architectures with unstructured groups of peers, and these groups are the structured in a larger topology (e.g. Skype).
P2P networks are totally decentralised. Peers participating in the overlay may leave the network ungracefully and at random time. To maintain the topology structure of a P2P network in case of node failures, it is mandatory that each node maintains several links to direct neighbour nodes. In Chord, e.g., each peer maintains a so-called “redundant successor list” which stabilises the P2P ring topology if one or more of the succeeding neighbour peers ungracefully leaves the P2P overlay.
FIG. 1a shows a prior art structured P2P overlay network N comprising a plurality of nodes 0, 20, 50, 87, 112, 140, 179, 200, 211, 223, 240. In particular, FIG. 1a illustrates a Chord ring N. The reference signs 0, 20, 50, 87, 112, 140, 179, 200, 211, 223, 240 of the nodes are meant to represent also the node IDs of the nodes 0, 20, 50, 87, 112, 140, 179, 200, 211, 223, 240. In Chord the nodes maintain direct connections to their predecessor and successor nodes, which results in a ring topology.
In the P2P Chord ring N, the ring topology structure is kept stable by using a successor list, which may also be called redundant successor list (=RSL). As shown in FIG. 1a, a first node 200 of the plurality of nodes 0, 20, 50, 87, 112, 140, 179, 200, 211, 223, 240 maintains a successor list specifying identifiers of two successor nodes 211, 223 subsequently succeeding the first node 200. If the first successor node 211 crashes and leaves the ring, as is shown in FIG. 1b, the first node 200 still has a link to the other successor node 223 listed in the successor list. By means of the redundancy of successor nodes in the successor list, the topology structure of the peer-to-peer overlay network can be maintained. If multiple subsequent successor nodes neighbouring the first node 200 crash and the successor list does not list enough successor nodes such that the ring can be closed, the topology structure cannot be maintained and the ring breaks. Consequently the stability of the ring topology depends on the number of successor nodes listed in the successor list: the more successor nodes the more stable the ring.